#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

typedef struct intNode
{
    int data;
    IN *lc, *rc;
} IN;

typedef struct inTree
{
    IN *root;
} iT;

void levelOrder(iT *tree)
{
    IN *curNode;
    queue<IN *> q;
    q.push(tree->root);
    while (!q.empty())
    {
        curNode = q.front();
        q.pop();
        printf("%d ", curNode->data);
        if (curNode->lc)
            q.push(curNode->lc);
        if (curNode->rc)
            q.push(curNode->rc);
    }
}

void PreOrder(iT *tree)
{
    IN *curNode;
    stack<IN *> s;
    s.push(tree->root);
    while (!s.empty())
    {
        curNode = s.top();
        s.pop();
        printf("%d ", curNode->data);
        if (curNode->rc)
            s.push(curNode->rc);
        if (curNode->lc)
            s.push(curNode->lc);
    }
}

void InOrder(iT *tree)
{
    IN *curNode;
    stack<IN *> s;
    s.push(tree->root);
    while (!s.empty())
    {
        if (curNode->lc)
        {
            s.push(curNode->lc);
            curNode = curNode->lc;
        }
        else
        {
            printf("%d ", curNode->data);
            s.pop();
            if (curNode->rc)
                s.push(curNode->rc);
        }
    }
}

void PostOrder(iT *tree)
{
    IN *curNode;
    stack<IN *> s;
    s.push(tree->root);
    while (!s.empty())
    {
        if (curNode->rc)
        {
            s.push(curNode->rc);
            curNode = curNode->rc;
        }
        else
        {
            printf("%d ", curNode->data);
            s.pop();
            if (curNode->lc)
                s.push(curNode->lc);
        }
    }
}

void InsertData(iT *tree, int data)
{
    IN *newNode = new IN();
    if (!tree->root)
    {
        tree->root = newNode;
        return;
    }
    IN *curNode;
    queue<IN *> queues;
    queues.push(tree->root);
    while (queues.empty())
    {
        curNode = queues.front();
        queues.pop();
        if (curNode->lc)
        {
            queues.push(curNode->lc);
        }
        else
        {
            curNode->lc = newNode;
            return;
        }
        if (curNode->rc)
        {
            queues.push(curNode->rc);
        }
        else
        {
            curNode->rc = newNode;

            return;
        }
    }
}

iT *init()
{
    iT *intree = new iT();

    return intree;
}
